package com.leetcode.LeetCode精选TOP面试题;

/**
 * @author 覃国强
 * @date 2022-05-23 17:17
 */
public class 题库_0042_接雨水 {

  static
  class Solution {
    public int trap(int[] height) {
      if (height == null || height.length < 3) {
        return 0;
      }

      int left = 0;
      int leftMax = 0;
      int right = height.length - 1;
      int rightMax = 0;
      int answer = 0;

      // left 与 right 的相遇一定是在峰值的地方，所以相遇的地方不需要计算雨水量
      while (left < right) {
        leftMax = Math.max(leftMax, height[left]);
        rightMax = Math.max(rightMax, height[right]);

        if (leftMax < rightMax) {
          answer += leftMax - height[left++];
        } else {
          answer += rightMax - height[right--];
        }
      }

      return answer;
    }
  }

}
